//现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。
//
// 给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如
//prerequisites[i] = [ai, bi] 表示想要学习课程 ai ，需要先完成课程 bi 。
//
// 请根据给出的总课程数 numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。
//
// 可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
//
//
//
// 示例 1:
//
//
//输入: numCourses = 2, prerequisites = [[1,0]]
//输出: [0,1]
//解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
//
// 示例 2:
//
//
//输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
//输出: [0,1,2,3] or [0,2,1,3]
//解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
// 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
//
//
// 示例 3:
//
//
//输入: numCourses = 1, prerequisites = []
//输出: [0]
//解释: 总共 1 门课，直接修第一门课就可。
//
//
//
// 提示:
//
//
// 1 <= numCourses <= 2000
// 0 <= prerequisites.length <= numCourses * (numCourses - 1)
// prerequisites[i].length == 2
// 0 <= ai, bi < numCourses
// ai != bi
// prerequisites 中不存在重复元素
//
//
//
//
//
// 注意：本题与主站 210 题相同：https://leetcode-cn.com/problems/course-schedule-ii/
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 👍 47 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    //? 两个map记录
    const edges = new Map(), indeg = new Map()
    for (let i = 0; i < numCourses; i++) {
        //? 存节点的边(只存连接比他大的数)
        if (!edges.has(i)) edges.set(i, [])
        //? 存节点的出现次数(作为更大的那个数的出现次数)
        if (!indeg.has(i)) indeg.set(i, 0)
    }
    for (let [a, b] of prerequisites) {
        //? 记录应该在b后出现的节点
        edges.get(b).push(a)
        //? 记录a应该在多少个数之前
        indeg.set(a, indeg.get(a) + 1)
    }
    //? 层序遍历队列和结果数组
    const queue = [], ans = []
    for (let [key, val] of indeg) {
        //? val为0 代表此课程一直出现在数组后一位 即需要最先完成的 从这个点开始
        //? 如果没有 代表G了
        if (val == 0) queue.push(key)
    }
    //? 层序遍历
    while(queue.length) {
        let node = queue.shift()
        //? 拿到此节点的边(应该在此节点后出现的节点)
        let arr = edges.get(node)
        ans.push(node)
        for (let i of arr) {
            //? 节点出现次数-1
            indeg.set(i, indeg.get(i) - 1)
            //? 减到0 代表i节点接下来不会再比任何剩下的数大 入queue
            //? 当然 这里不能再继续入队了 代表结束了或者不满足题意 则跳出了
            if (indeg.get(i) == 0) {
                queue.push(i)
            }
        }
    }
    return ans.length == numCourses ? ans : []
};


//leetcode submit region end(Prohibit modification and deletion)
